//
// Created by Administrator on 2021/4/15.
//
/*在二叉树中，根节点位于深度 0 处，每个深度为 k 的节点的子节点位于深度 k+1 处。

如果二叉树的两个节点深度相同，但 父节点不同 ，则它们是一对堂兄弟节点。

我们给出了具有唯一值的二叉树的根节点 root ，以及树中两个不同节点的值 x 和 y 。

只有与值 x 和 y 对应的节点是堂兄弟节点时，才返回 true 。否则，返回 false。


示例 1：


输入：root = [1,2,3,4], x = 4, y = 3
输出：false
示例 2：


输入：root = [1,2,3,null,4,null,5], x = 5, y = 4
输出：true
示例 3：



输入：root = [1,2,3,null,4], x = 2, y = 3
输出：false

提示：

二叉树的节点数介于2 到100之间。
每个节点的值都是唯一的、范围为1 到100的整数。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/cousins-in-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。*/

#include <vector>
#include <queue>
#include <iostream>
#include <algorithm>
#include <numeric>

using namespace std;

struct TreeNode {
    int val; // 节点值
    TreeNode *left; // 左子节点
    TreeNode *right; // 右子节点

    TreeNode() : val(0), left(nullptr), right(nullptr) {}

    explicit TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}

};

class Solution {
public:
    bool isCousins(TreeNode *root, int x, int y) {
        // dfs 标记每个节点的父节点和层数
        unordered_map<int, int> parent;
        unordered_map<int, int> level;
        dfs(root, parent, level, 0);
        return parent[x] != parent[y] and level[x] == level[y];
    }

    void dfs(TreeNode *root, unordered_map<int, int> &p, unordered_map<int, int> &l, int curLevel) {
        if (!root) return;
        l[root->val] = curLevel;
        if (root->left) {
            p[root->left->val] = root->val;
        }
        if (root->right) {
            p[root->right->val] = root->val;
        }
        dfs(root->left, p, l, curLevel + 1);
        dfs(root->right, p, l, curLevel + 1);
    }
};

int main() {
    auto t5 = TreeNode(5);
    auto t4 = TreeNode(4);
    auto t3 = TreeNode(3, nullptr, &t5);
    auto t2 = TreeNode(2, &t4, nullptr);
    auto t1 = TreeNode(1, &t2, &t3);
    Solution sol;
    cout << (sol.isCousins(&t1, 5, 4) ? "true" : "false");
    return 0;
}